덱 (자료 구조)
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
덱(Deque)은 'Double-ended queue'의 약자로, 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조이다. 입력 제한 덱과 출력 제한 덱으로 구분되며, 큐와 스택을 덱을 사용하여 구현할 수 있다. 덱은 동적 배열 또는 이중 연결 리스트를 사용하여 구현할 수 있으며, 다양한 프로그래밍 언어에서 지원된다. 덱은 브라우징 기록 저장, 작업 훔치기 알고리즘 등 다양한 응용 분야에서 활용된다.
더 읽어볼만한 페이지
- 추상 자료형 - 리스트 (컴퓨팅)
리스트는 컴퓨터 과학에서 항목들을 순서대로 저장하고 관리하는 기본적인 자료 구조이며, 다양한 연산을 지원하고 연결 리스트나 동적 배열 등으로 구현되며 큐, 스택 등 다른 자료형의 기반이 된다. - 추상 자료형 - 스택
스택은 후입선출(LIFO) 원칙에 따라 데이터를 관리하는 추상 자료형으로, push 연산으로 데이터를 쌓고 pop 연산으로 가장 최근 데이터를 제거하며, 서브루틴 호출 관리, 수식 평가, 백트래킹 등에 활용된다. - 자료 구조 - 라우팅 테이블
라우팅 테이블은 네트워크에서 데이터 전송 시 최적 경로를 결정하는 핵심 데이터베이스로, 라우터가 목적지 IP 주소를 기반으로 다음 홉을 결정하며 직접 연결 및 원격 네트워크 경로 정보를 저장하고 동적 라우팅 또는 수동 설정으로 관리된다. - 자료 구조 - 스택
스택은 후입선출(LIFO) 원칙에 따라 데이터를 관리하는 추상 자료형으로, push 연산으로 데이터를 쌓고 pop 연산으로 가장 최근 데이터를 제거하며, 서브루틴 호출 관리, 수식 평가, 백트래킹 등에 활용된다.
| 덱 (자료 구조) |
|---|
2. 명칭
덱(deque)은 '디큐(dequeue)'로 표기되기도 하지만, "큐에서 제거하다"라는 동사로도 사용되기 때문에, 일반적으로 기술 문헌이나 기술 문서에서는 이 사용법을 권장하지 않는다.[1] 그럼에도 불구하고, 일부 라이브러리와 아호, 홉크로프트, 울만 등은 저서 ''자료 구조와 알고리즘''에서 '디큐'로 표기한다.[1] 존 미첼은 저서 ''프로그래밍 언어 개념''에서 이 용어를 사용한다.[1]
덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다. 덱은 크게 입력 제한 덱과 출력 제한 덱으로 나눌 수 있다.
3. 종류
큐와 스택은 덱의 특수한 경우이며, 덱을 사용하여 구현할 수 있다.[1]
3. 1. 입력 제한 덱 (Scroll)
삭제는 양쪽 끝에서 가능하지만, 삽입은 한쪽 끝에서만 할 수 있는 덱을 입력 제한 덱이라고 한다. 컴퓨팅에서 가장 기본적인 일반적인 리스트 유형인 큐와 스택은 덱의 특수한 경우로 간주될 수 있으며, 덱을 사용하여 구현할 수 있다.[1]
3. 2. 출력 제한 덱 (Shelf)
출력 제한 덱은 삽입은 양쪽 끝에서 가능하지만, 삭제는 한쪽 끝에서만 가능한 덱이다. 요소의 추가는 양쪽 끝에서 가능하지만, 꺼내기는 한쪽에서만 가능하다는 특징을 가진다.[1]
4. 연산
덱의 기본 연산은 양쪽 끝에서의 삽입(push)과 삭제(pop)이다. 엿보기(peek) 연산을 통해 삭제하지 않고 해당 끝의 값을 확인할 수 있다.
다음은 주요 프로그래밍 언어에서의 덱 연산 명칭이다.
| 연산 | 일반적인 이름 | Ada | C++ | Java | Perl | PHP | Python | Ruby | Rust | JavaScript |
|---|---|---|---|---|---|---|---|---|---|---|
| 뒤쪽에 요소 삽입 | inject, snoc, push | Append | push_back | offerLast | push | array_push | append | push | push_back | push |
| 앞쪽에 요소 삽입 | push, cons | Prepend | push_front | offerFirst | unshift | array_unshift | appendleft | unshift | push_front | unshift |
| 마지막 요소 제거 | eject | Delete_Last | pop_back | pollLast | pop | array_pop | pop | pop | pop_back | pop |
| 첫 번째 요소 제거 | pop | Delete_First | pop_front | pollFirst | shift | array_shift | popleft | shift | pop_front | shift |
| 마지막 요소 확인 | peek | Last_Element | back | peekLast | $array[-1] | end | | last | back | |
| 첫 번째 요소 확인 | First_Element | front | peekFirst | $array[0] | reset | | first | front | |
5. 구현
덱은 동적 배열을 수정하거나 이중 연결 리스트를 사용하여 효율적으로 구현할 수 있다. 순수 함수형 자료 구조로도 구현할 수 있다.
5. 1. 동적 배열 구현
동적 배열을 수정하여 덱(자료 구조)을 구현할 수 있으며, 이를 '배열 덱'이라고도 한다. 배열 덱은 상수 시간 임의 접근과 우수한 참조 지역성을 가지며, 양쪽 끝에서 분할 상환 상수 시간으로 삽입/삭제가 가능하다. 구현 방법은 다음과 같다.- 링 버퍼에 덱 내용을 저장하고, 버퍼가 가득 찼을 때만 크기를 조정한다. 크기 조정 빈도를 줄일 수 있다.
- 기본 배열의 중앙에서 덱 내용을 할당하고, 양쪽 끝에 도달하면 배열 크기를 조정한다. 한쪽 끝에만 요소가 삽입될 경우 공간 낭비가 발생할 수 있다.
- 여러 개의 작은 배열에 내용을 저장하고, 시작 또는 끝에 추가 배열을 할당한다. 인덱싱은 각 작은 배열을 가리키는 포인터를 포함하는 동적 배열을 통해 구현된다.
5. 2. 순수 함수형 구현
순수 함수형 자료 구조로 덱(Deque)을 구현할 수 있다.[3] 이에는 두 가지 버전이 있다.첫 번째는 '''실시간 덱'''으로, 최악의 시간 내에 연산을 수행하면서 덱이 영구적 자료 구조가 되도록 한다. 하지만 이 구현은 레이지 평가를 사용한 메모이제이션이 있는 지연 리스트를 필요로 한다.
두 번째 버전은 지연 리스트나 메모이제이션을 사용하지 않는다. 이 버전은 영속성을 사용하지 않는 경우 분할 상환 분석 시간이 이지만, 연산의 최악 시간 복잡도는 이다. 여기서 는 덱에 있는 요소의 개수이다.
리스트 l영어에 대해, 은 리스트의 길이를, `NIL`은 빈 리스트를, `CONS(h, t)`는 헤드가 h영어이고 테일이 t영어인 리스트를 나타낸다. 함수 drop(i, l)영어과 take(i, l)영어은 리스트 l영어에서 처음 i영어개의 요소를 제외한 리스트와, l영어의 처음 i영어개의 요소를 각각 반환한다. 만약 < i영어이면, 빈 리스트와 l영어을 각각 반환한다.
덱은 6개의 튜플 `(len_front, front, tail_front, len_rear, rear, tail_rear)`로 표현된다. 여기서 front영어는 큐의 앞부분을 포함하는 연결 리스트이며 길이는 len_front영어이다. rear영어는 큐의 뒷부분의 역순을 나타내는 연결 리스트이며 길이는 len_rear영어이다. ≤ 2+1과 ≤ 2+1이 보장된다. 이는 앞부분과 뒷부분 모두 요소의 3분의 1 마이너스 1에서 3분의 2 플러스 1 사이의 요소를 포함한다는 것을 의미한다. tail_front영어 및 tail_rear영어는 front영어와 rear영어의 꼬리이며, 일부 지연된 연산이 강제되는 시점을 예약할 수 있게 한다. 덱이 앞쪽 리스트에 n영어개의 요소와 뒤쪽 리스트에 n영어개의 요소를 포함하는 경우, i영어번의 삽입과 d영어번의 삭제 후에도 부등식 불변성은 `(i+d) ≤ n/2`일 때 유지된다. 즉, 각 재균형 조정 사이에 최대 n/2영어번의 연산이 발생할 수 있다.
큐의 앞부분에 영향을 미치는 연산(cons, head, tail)의 구현은 다음과 같다. (뒷부분에 영향을 미치는 연산은 대칭적으로 정의된다.)
```sml
empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
(len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
(len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty
```
위 구현은 불변성을 반드시 준수하지는 않는다. 앞부분이 비어 있으면 뒷부분에 최대 하나의 요소가 있다는 불변성은 사용한다.
`insert'` 또는 `tail'`이 불변성을 깨뜨린 경우, `balance` 메서드를 사용하여 덱을 재균형 조정할 수 있다. `insert` 및 `tail` 메서드는 먼저 `insert'` 및 `tail'`을 적용한 다음 `balance`를 적용하여 정의한다.
```sml
fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
let floor_half_len = (len_front + len_rear) / 2 in
let ceil_half_len = len_front + len_rear - floor_half_len in
if len_front > 2*len_rear+1 then
let val front' = take(ceil_half_len, front)
val rear' = rotateDrop(rear, floor_half_len, front)
in (ceil_half_len, front', front', floor_half_len, rear', rear')
else if len_front > 2*len_rear+1 then
let val rear' = take(floor_half_len, rear)
val front' = rotateDrop(front, ceil_half_len, rear)
in (ceil_half_len, front', front', floor_half_len, rear', rear')
else q
```
`rotateDrop(front, i, rear))`는 front영어와 drop(i, rear)영어의 연결을 반환한다. front' = rotateDrop(front, ceil_half_len, rear)영어는 front'영어에 front영어의 내용과 rear'영어에 아직 없는 rear영어의 내용을 넣는다. 각 `tail'` 및 각 `insert'` 연산 중에 두 번의 삭제가 수행되도록 지연 평가를 사용하여 요소를 두 개씩 삭제한다.
```sml
fun rotateDrop(front, i, rear) =
if i < 2 then rotateRev(front, drop(i, rear), NIL)
else let CONS(x, front') = front in
CONS(x, rotateDrop(front', j-2, drop(2, rear)))
```
`rotateRev(front, middle, rear)`는 앞부분, 뒤집힌 중간 부분, 뒷부분을 반환하는 함수이다. 이 함수는 각 `insert'` 및 `tail'` 중에 실행되고 상수 시간이 걸리도록 단계별로 계산할 수 있도록 지연 평가를 사용하여 정의된다. 이 함수는 -2가 2 또는 3이라는 불변성을 사용한다.
```sml
fun rotateRev(NIL, rear, a) =
reverse(rear)++a
fun rotateRev(CONS(x, front), rear, a) =
CONS(x, rotateRev(front, drop(2, rear), reverse(take(2, rear))++a))
```
여기서 `++`는 두 개의 리스트를 연결하는 함수이다.
지연 평가를 사용하지 않는 구현은 상각 시간으로 큐의 비영속적인 구현이 된다. 이 경우, 덱의 표현에서 tail_front영어 및 tail_rear영어 리스트를 제거할 수 있다.
6. 언어 지원
에이다는 동적 배열 구현을 위한 제네릭 패키지 `Ada.Containers.Vectors`와 연결 리스트 구현을 위한 `Ada.Containers.Doubly_Linked_Lists`를 제공한다.
C++의 STL는 `std::deque`와 `std::list` 클래스 템플릿을 제공한다. `std::deque`는 일반적으로 여러 개의 고정 크기 배열을 사용하여 구현되며, 양쪽 끝과 임의 접근을 지원한다. 중간 삽입/삭제는 *O*(*n*) 시간이 걸리는 반면, 양쪽 끝 삽입/삭제는 *O*(1)이다.
Java 6부터 Java 컬렉션 프레임워크는 `java.util.Deque` 인터페이스를 제공하며, `java.util.ArrayDeque`와 `java.util.LinkedList` 클래스로 구현된다. `ArrayDeque`는 동적 배열, `LinkedList`는 연결 리스트를 사용한다.
파이썬은 `collections` 모듈의 `collections.deque` 객체를 통해 덱을 지원한다.
PHP는 SPL 확장의 `SplDoublyLinkedList` 클래스를 통해 덱 자료 구조를 구현할 수 있다.
하스켈은 `Data.Sequence` 모듈에서 덱 구조를 구현한다.
Rust는 `std::collections::VecDeque`를 통해 덱을 지원한다.
| 언어 | 지원 여부 | 구현 방식 | 비고 |
|---|---|---|---|
| 에이다 | 지원 | `Ada.Containers.Vectors`, `Ada.Containers.Doubly_Linked_Lists` | 제네릭 패키지 |
| C++ | 지원 | `std::deque`, `std::list` | STL |
| Java | 지원 | `java.util.Deque` 인터페이스, `java.util.ArrayDeque`, `java.util.LinkedList` | Java 6 이상 |
| 파이썬 | 지원 | `collections.deque` | |
| PHP | 지원 | `SplDoublyLinkedList` 클래스 | PHP 5.3 이상, SPL 확장 |
| 하스켈 | 지원 | `Data.Sequence` 모듈 | |
| Rust | 지원 | `std::collections::VecDeque` |
7. 복잡도
- 이중 연결 리스트로 구현할 경우, 할당/해제 오버헤드가 없다고 가정하면 모든 덱 연산의 시간 복잡도는 O(1)이다. 반복자가 주어졌을 때 중간 삽입 또는 삭제의 시간 복잡도 역시 O(1)이다. 그러나 인덱스를 통한 임의 접근의 시간 복잡도는 O(n)이다.
- 확장 배열로 구현할 경우, 모든 덱 연산의 상각 시간 복잡도는 O(1)이다. 인덱스를 통한 임의 접근의 시간 복잡도 역시 O(1)이다. 그러나 중간 삽입 또는 삭제의 시간 복잡도는 O(n)이다.
8. 응용
덱은 브라우징 기록을 저장하는 데 사용할 수 있다. 새로운 웹사이트는 덱의 끝에 추가되고, 기록이 너무 커지면 가장 오래된 항목이 삭제된다. 사용자가 지난 한 시간 동안의 브라우징 기록을 지우도록 요청하면 가장 최근에 추가된 항목이 제거된다.
덱을 사용할 수 있는 또 다른 예는 작업 훔치기 알고리즘이다.[9] 이 알고리즘은 여러 프로세서에 대한 작업 스케줄링을 구현한다. 각 프로세서마다 실행할 스레드가 있는 별도의 덱이 유지된다. 다음 스레드를 실행하기 위해 프로세서는 덱에서 첫 번째 요소를 가져온다("첫 번째 요소 제거" 덱 연산 사용). 현재 스레드가 분기되면 덱의 맨 앞으로 다시 넣고("앞쪽에 요소 삽입") 새 스레드가 실행된다. 프로세서 중 하나가 자체 스레드 실행을 마치면(즉, 덱이 비어 있으면) 다른 프로세서에서 스레드를 "훔칠" 수 있다. 다른 프로세서의 덱에서 마지막 요소를 가져와("마지막 요소 제거") 실행한다. 작업 훔치기 알고리즘은 인텔의 Threading Building Blocks(TBB) 라이브러리에서 사용된다.
참조
[1]
서적
"C++ in One Hour a Day, Sams Teach Yourself"
Sams Publishing
[2]
서적
The Art of Computer Programming
Addison-Wesley
[3]
학위논문
Purely Functional Data Structures
https://www.cs.cmu.e[...]
Carnegie Mellon University
1996-09
[4]
논문
Confluently persistent deques via data structural bootstrapping
1995-05
[5]
논문
Purely functional representations of catenable sorted lists
1996-05
[6]
간행물
Catenable double-ended queues
https://dl.acm.org/d[...]
1997-08
[7]
간행물
Simple Confluently Persistent Catenable Lists
https://epubs.siam.o[...]
2000
[8]
간행물
Notes on Catenable Deques in Pure Lisp
https://www.cs.princ[...]
Princetown University
2003-08
[9]
학술지
Scheduling multithreaded computations by work stealing
http://supertech.csa[...]
[10]
서적
The Art of Computer Programming
Addison-Wesley
[11]
서적
Effective STL STLを効果的に使いこなす50の鉄則
ピアソン・エデュケーション
[12]
서적
Job Scheduling Strategies for Parallel Processing: 12th International Workshop, JSSPP 2006
Springer
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com